package com.hy.stack;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class MyStack {

    /**
     * 栈与队列：用队列实现栈还有点别扭
     * 225. 用队列实现栈
     *
     * 使用队列实现栈的下列操作：
     *
     * push(x) -- 元素 x 入栈
     * pop() -- 移除栈顶元素
     * top() -- 获取栈顶元素
     * empty() -- 返回栈是否为空
     *
     * 思路
     * （这里要强调是单向队列）
     *
     * 有的同学可能疑惑这种题目有什么实际工程意义，其实很多算法题目主要是对知识点的考察和教学意义远大于其工程实践的意义，所以面试题也是这样！
     *
     * 刚刚做过栈与队列：我用栈来实现队列怎么样？的同学可能依然想着用一个输入队列，一个输出队列，就可以模拟栈的功能，仔细想一下还真不行！
     *
     * 队列模拟栈，其实一个队列就够了，那么我们先说一说两个队列来实现栈的思路。
     *
     * 队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。
     *
     * 所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。
     *
     * 但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用又来备份的！
     *
     * 如下面动画所示，用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。
     *
     *
     */
    // 和栈中保持一样元素的队列
    Queue<Integer> q1;
    // 辅助队列
    Queue<Integer> q2;

    /** Initialize your data structure here. */
    public MyStack(){
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }


    //Push element x onto stack.
    public void push(int x){
        q2.offer(x);
        while (!q1.isEmpty()){
            // offer() 彺队列中添加元素
            // poll() 检索并删除此队列的头部
            q2.offer(q1.poll());
        }
        // 队列1  队列2 交换元素
        Queue<Integer> tempQueue;
        tempQueue = q1;
        q1 = q2;
        // 最后交换queue1和queue2，将元素都放到queue1中
        q2 = tempQueue;
    }
    // Removes the element from in front of queue and returns that element.
    public int pop (){
        return q1.poll();
    }
    //  Get the front element.
    public int peek(){
        return q1.peek();
    }
    // Returns whether the queue is empty.
    public boolean empty(){
        return q1.isEmpty();
    }


    public static void main(String[] args) {
        // 用队列  模拟栈（先进后出）
        MyStack myQueue = new MyStack();
        myQueue.push(1);
        myQueue.push(2);
        System.out.println("栈是否为空："+myQueue.empty());
        System.out.println("出栈数据2： "+myQueue.pop());
        myQueue.push(3);
        myQueue.push(4);
        System.out.println("出栈数据4： "+myQueue.pop());
        System.out.println("出栈数据3： "+myQueue.pop());
        System.out.println("获取栈中最前面的元素："+myQueue.peek());
        System.out.println("出栈数据1： "+myQueue.pop());
        System.out.println("栈是否为空："+myQueue.empty());

    }
}
